Broadcast or read-only media containing video data may also comprise subpicture data streams, containing textual or graphical information needed to provide subtitles, glyphs or animation for any particular purpose, e.g. menu buttons. Since displaying of such information may usually be enabled or disabled, it is overlaid on the associated video image as an additional layer, and is implemented as one or more rectangular areas called regions. Such region has specified a set of attributes, like e.g. area size, area position or background color. Due to the region being overlaid on the video image, its background is often defined to be transparent so that the video image can be seen, or multiple subpicture layers can be overlaid. Further, a subtitle region may be broader than the associated image, so that only a portion of the subtitle region is visible, and the visible portion of the region is shifted e.g. from right to left through the whole subtitle area, which looks as if the subtitles would shift through the display. This method of pixel based subtitling is described in the European Patent application EP02025474.4 and is called cropping. Subtitles were originally meant as a support for handicapped people, or to save the costs for translating a film into rarely used languages, and therefore for pure subtitle text it would be enough if the subtitle data stream contained e.g. ASCII coded characters. But subtitles today contain also other elements, up to high-resolution images, glyphs or animated graphical objects. Handling of such elements is easier if the subtitling stream is coded in bitmap format, with the lines of an area and the pixels within a line being coded and decoded successively. This format contains much redundancy, e.g. when successive pixels have the same color value. This redundancy can be reduced by various coding methods, e.g. run-length encoding (RLE). RLE is often used when sequences of data have the same value, and its basic ideas are to code the sequence length and the value separately, and to code the most frequent code words as short as possible.
Particularly when encoding the subtitle layer for 1920×1280 pixels high-definition video (HDTV), a coding algorithm that is optimized for this purpose is needed to reduce the required amount of data.